Alon and Mohar (2002) posed the following problem: among all graphs $G$ ofmaximum degree at most $d$ and girth at least $g$, what is the largest possiblevalue of $\chi(G^t)$, the chromatic number of the $t$th power of $G$? For $t\ge3$, we provide several upper and lower bounds concerning this problem, all ofwhich are sharp up to a constant factor as $d\to \infty$. The upper bounds relyin part on the probabilistic method, while the lower bounds are various directconstructions whose building blocks are incidence structures.
展开▼
机译：Alon和Mohar（2002）提出了以下问题：在所有图中，最大度数的$ G $最多$ d $和周长至少$ g $，$ \ chi（G ^ t）$的最大可能值是色度。 $ G $的$ t $ th次方的个数？对于$ t \ ge3 $，我们提供了有关此问题的几个上限和下限，所有这些上限和下限都以$ d \至\ infty $的常数为单位。上限部分取决于概率方法，而下限是各种直接构造，其构造块是入射结构。
展开▼
